package com.leecode;

import java.util.ArrayList;

/**
 * 给定一个非负整数数组，a1, a2, ..., an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。
 * <p>
 * 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。
 * <p>
 * <p>
 * <p>
 * 示例：
 * <p>
 * 输入：nums: [1, 1, 1, 1, 1], S: 3
 * 输出：5
 * 解释：
 * <p>
 * -1+1+1+1+1 = 3
 * +1-1+1+1+1 = 3
 * +1+1-1+1+1 = 3
 * +1+1+1-1+1 = 3
 * +1+1+1+1-1 = 3
 */
public class Leet494 {
	public static void main(String[] args) {
		System.out.println(new Leet494().findTargetSumWays(new int[]{1, 1, 1}, 1));
	}

	int count = 0;

	public int findTargetSumWays(int[] nums, int S) {
		int sum = 0;
		Integer countInteger = new Integer(0);
		ArrayList arrayList = new ArrayList();
		backTrace(nums, 0, 0, S, count, arrayList, countInteger);
		return this.count;
	}

	public void backTrace(int[] nums, int b, int sum, int tar, int count, ArrayList arrayList, Integer countInteger) {
		if (b > nums.length - 1) {
			if (sum == tar) {
				/**
				 * 有意思,算是基础中的坑吧,
				 */
				count++;//它传递不了count的累加,最里面的stack frame中的count自增,接着就弹出,外层的stackf还是0
				this.count++;
				arrayList.add(1);//传递"累加"
				countInteger += 1;//还是0,不传递"累加",128(Integet@488)和129(Integer@490)是两个不同对象,弹栈后@490对象消失
			}
			return;
		}

		for (int a = 0; a < 2; a++) {
			if (a == 0) {
				backTrace(nums, b + 1, sum - nums[b], tar, count, arrayList, countInteger);
			} else {
				backTrace(nums, b + 1, sum + nums[b], tar, count, arrayList, countInteger);
			}
		}
	}
}
